package 数据结构专栏.简单级别;

/**
 * @DESC 给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
 * <p>
 * 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
 * <p>
 * 链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array
 * https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/solution/shan-chu-pai-xu-shu-zu-zhong-de-zhong-fu-xiang-by-/
 * @Author tzq
 * @Date 2020-03-26 19:33
 **/
public class _26_删除排序数组中的重复项 {

    public static void main(String[] args) {
//        int[] arr = new int[]{1, 1, 3};
//        System.out.println(removeDuplicates(arr));
//
//        int[] arr2 = new int[]{1, 2};
//        System.out.println(removeDuplicates(arr2));

        // 思路：
        // 因为数组有序，因此只需要去对比 nums[i] 和当前去重数组的最大值是否相等即可。我们用一个 temp 变量保存去重数组的最大值。
        // 如果二者不等，则说明是一个新的数据。我们就需要把这个新数据放到去重数组的最后，并且修改 temp 变量的值，再修改当前去重数组的长度变量 len。直到遍历完，就得到了结果
        int[] nums = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
        int temp = nums[0];
        int len = 1; // 记录数组长度
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != temp) { // 如果当前元素与去重的最大值不等
                nums[len] = nums[i]; // 新元素放入去重数组中
                temp = nums[i]; // 更新去重数组的最大值
                len++;
            }
        }
        System.out.println(len);

        for (int i = 0; i < len; i++) {
            System.out.print(nums[i] + " ");
        }


    }

    /**
     * 使用双指针来做
     * <p>
     * 拿慢指针锁指向的值和快指针指向的值进行比较，如果不等，则将快指针锁指向值赋给慢指针所指向值，且慢指针向前挪动一位
     *
     * @param nums
     * @return
     */
    public static int removeDuplicates(int[] nums) {

        if (nums.length == 0) return 0;

        // 定义初始慢指针
        int pre = 0;

        // 快指针
        for (int i = 1; i < nums.length; i++) {
            if (nums[pre] != nums[i]) {
                pre++;
                nums[pre] = nums[i];

            }
        }


        return pre + 1;
    }


    public static void removeDuplicates3(int[] nums) {
        int temp = nums[0];
        int len = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != temp) {
                nums[len] = nums[i];
                temp = nums[i];
                len++;
            }
        }
    }


}
